package main

import "math"

func quickMulti(x int, y int) int {
	if y == 1 {
		return x
	}
	if y == -1 {
		return -x
	}
	x2 := quickMulti(x, y>>1)
	if y&1 == 1 { // y 为奇数
		return x2 + x2 + x
	}
	return x2 + x2
}

func divide(dividend, divisor int) int {
	if dividend == math.MinInt32 { // 考虑被除数为最小值的情况
		if divisor == 1 {
			return math.MinInt32
		}
		if divisor == -1 {
			return math.MaxInt32
		}
	}
	if divisor == math.MinInt32 { // 考虑除数为最小值的情况
		if dividend == math.MinInt32 {
			return 1
		}
		return 0
	}
	if dividend == 0 { // 考虑被除数为 0 的情况
		return 0
	}

	// 一般情况，使用二分查找
	// 将所有的正数取相反数，这样就只需要考虑一种情况
	rev := false
	if dividend > 0 {
		dividend = -dividend
		rev = !rev
	}
	if divisor > 0 {
		divisor = -divisor
		rev = !rev
	}

	ans := 0
	left, right := 1, math.MaxInt32
	for left <= right {
		mid := left + (right-left)>>1 // 注意溢出，并且不能使用除法
		multi := quickMulti(divisor, mid)
		if multi >= dividend { // multi, dividend 都是负数 multi * mid >= dividend
			// mid 过大
			ans = mid
			if mid == math.MaxInt32 { // 注意溢出
				break
			}
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if rev {
		return -ans
	}
	return ans
}

func main() {
	println(quickMulti(6, -9))
	println(divide(5, 2))
}
